|
In mathematics and computer science, a morphic word or substitutive word is an infinite sequence of symbols which is constructed from a particular class of endomorphism of a free monoid. Every automatic sequence is morphic.〔 ==Definition== Let ''f'' be an endomorphism of the free monoid ''A''∗ on an alphabet ''A'' with the property that there is a letter ''a'' such that ''f''(''a'') = ''as'' for a non-empty string ''s'': we say that ''f'' is prolongable at ''a''. The word : is a pure morphic or pure substitutive word. It is clearly a fixed point of the endomorphism ''f'': the unique such sequence beginning with the letter ''a''.〔Lothaire (2011) p. 10〕〔Honkala (2010) p.505〕 In general, a morphic word is the image of a pure morphic word under a coding.〔 If a morphic word is constructed as the fixed point of a prolongable ''k''-uniform morphism on ''A''∗ then the word is ''k''-automatic. The ''n''-th term in such a sequence can be produced by a finite state automaton reading the digits of ''n'' in base ''k''.〔 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Morphic word」の詳細全文を読む スポンサード リンク
|